package com.hdu.hot100.graph;

import java.util.ArrayList;
import java.util.List;

public class lc207 {
    class Solution {
        public boolean canFinish(int numCourses, int[][] prerequisites)
        {
             int[] inqueue = new int[numCourses];
             List<List<Integer>> g = new ArrayList<>();
             for (int i = 0; i < numCourses; i++)
             {
                 g.add(new ArrayList<>());
             }
             for (int[] p : prerequisites)
             {
                 g.get(p[1]).add(p[0]);
                 inqueue[p[0]]++;
             }
             int[] q = new int[numCourses];
             int head = 0, tail = 0;
             for (int i = 0; i < numCourses; i++)
             {
                 if (inqueue[i] == 0)
                 {
                     q[tail++] = i;
                 }
             }
             int fillCount = 0;
             while (head < tail)
             {
                 int cur = q[head++];
                 fillCount++;
                 for (int next : g.get(cur))
                 {
                     if (--inqueue[next] == 0)
                     {
                         q[tail++] = next;
                     }
                 }
             }

             return fillCount == numCourses;
        }
    }
}
